Field of the Invention
The present invention relates to a technique of performing projection operation using random numbers.
Description of the Related Art
Dimension reduction/identification technology based on random projection is attracting attention. For example, patent literature 1 (Japanese Patent Laid-Open No. 2013-68884) discloses a technique of efficiently generating a hash function based on a random number. Also, a non-patent literature 1 (“Random projection in dimensionality reduction: Applications to image and text data”, Bingham, KDD2001) discloses a case in which random projection is applied to dimension reduction of image data or text data. Non-patent literature 2 (“Beyond simple features: A large-scale feature search approach to unconstrained face recognition”, Nicolas Pinto, David Cox, Automatic Face & Gesture Recognition and Workshops (FG 2011), 2011 IEEE International Conference on) discloses a technique related to object recognition using a filter based on a random number.
In random projection, a feature vector is projected onto a lower-dimensional space using base vectors generated based on random numbers. In general, when a projection operation is implemented, processing is performed with reference to base vectors (base vectors additionally calculated in advance) stored in a storage device, as disclosed in patent literature 1.
An example of the arrangement of a conventional identification apparatus using random projection will be described with reference to a block diagram shown in FIG. 2. Hardware 201 of accelerating identification processing includes a feature extraction processing unit 202, an inner product operation processing unit 203, and an identification processing unit 204. The inner product operation processing unit 203 transforms a feature vector generated by the feature extraction processing unit 202 into a lower-dimensional projection vector (in this case, processing is performed by random projection using random numbers). The inner product operation processing unit 203 executes a projection operation with reference to base vectors stored in an external memory 206 via a system bus 205. The external memory 206 is implemented by a low-speed mass memory such as a DRAM (Dynamic Random Access Memory). In a low-end system, due to the limitations on the bandwidth (the data transfer amount per unit time) of the system bus 205 and access delay to the external memory 206, the time taken to transfer the base vectors stored in the external memory 206 may exceed a processing time. Since the external memory 206 is generally shared with another processing (not shown), a bandwidth required for the system bus 205 is desirably narrow.
To decrease the transfer cost (necessary bandwidth) of the base vectors, a random number generator 302 may be incorporated in accelerator hardware 301, as shown in FIG. 3. If all the base vectors are formed from random number sequences, such implementation method may be adopted. However, as described in patent literature 1 and non-patent literature 2, if random number sequences which have been selected from a plurality of random number sequences under a desired condition are set as base vectors, the method shown in FIG. 3 cannot be applied.